package com.it.data_tree.tree.binaryTree;

import java.util.Arrays;

/**
 * @Author: Coke
 * @DateTime: 2023/04/16/18:58
 * @注释: 根据遍历结果建树
 **/
public class CreateBinaryTree {
    
    /**
     * @作者: Coke
     * @注释: 根据前中遍历结果建树
     * @DateTime: 2023/4/16 19:00
     *
     * @param preOrder:  前序遍历结果集合
     * @param inOrder:   中序遍历结果集合
     * @return Node
     */
    /*
    *  preOrder = {1, 2, 4, 3, 6, 7}
    *  inOrder =  {4, 2, 1, 6, 3, 7}
    *
    *  根 1
    *    前序      中序
    * 左  2,4        4,2
    * 右  3,6,7      6,3,7
    *
    *   根 2
    * 左 4
    *
    *   根 3
    * 左 6
    * 右 7
    * */
    public static Node createTreeByPreAndIn(int[] preOrder, int[] inOrder){
        if (preOrder.length == 0){
            return null;
        }
        // 创建根节点
        int rootValue = preOrder[0];
        Node node = new Node(rootValue);
        // 区分左右子树
        for (int i = 0; i < inOrder.length; i++) {
            if (inOrder[i] == rootValue){
                // 左子树： 0 ~ i-1 左子树
                // 右子树： i+1 ~ inOrder.length -1 右子树
                // 使用数组拷贝出中序的左子树 和 右子树
                int[] inLeft = Arrays.copyOfRange(inOrder, 0, i);
                int[] inRight = Arrays.copyOfRange(inOrder, i + 1, inOrder.length);
    
                //使用数组拷贝出前序的左子树
                int[] preLeft = Arrays.copyOfRange(preOrder, 1, i + 1);
                int[] preRight = Arrays.copyOfRange(preOrder, i + 1, inOrder.length);
    
                Node rootLeft = createTreeByPreAndIn(preLeft, inLeft);
                Node rootRight = createTreeByPreAndIn(preRight, inRight);
                node.setLeft(rootLeft);
                node.setRight(rootRight);
                break;
            }
        }
        return node;
    }
    
    /**
     * @作者: Coke
     * @注释: 根据中后序遍历结果建树
     * @DateTime: 2023/4/16 19:59
     *
     * @param inOrder: 中序遍历结果集合
     * @param postOrder: 后序遍历结果集合
     * @return Node
     */
    /*
    *  中序：inOrder =  {4, 2, 1, 6, 3, 7}
    *  后序：postOrder = {4, 2, 6, 7, 3, 1}
    *
    *   根 1
    *     中序         后序
    * 左：4, 2        4, 2
    * 右：6, 3, 7     6, 7, 3
    *
    *   根2
    * 左：4
    *
    * 根3
    * 左：6
    * 右：7
    * */
    public static Node createTreeByInAndPost(int[] inOrder, int[] postOrder){
        if (inOrder.length == 0){
            return null;
        }
        // 创建根节点
        int rootValue = postOrder[postOrder.length - 1];
        Node node = new Node(rootValue);
        
        // 区分左右子节点
        for (int i = 0; i < inOrder.length; i++) {
            if (inOrder[i] == rootValue){
                // 左：0 ~ i-1 [4, 2]
                // 右：i+1 ~ inOrder.length -1
                // 中序的左右子节点
                int[] inLeft = Arrays.copyOfRange(inOrder, 0, i);
                int[] inRight = Arrays.copyOfRange(inOrder, i + 1, inOrder.length);
    
                // 后序的左右子节点
                int[] postLeft = Arrays.copyOfRange(postOrder, 0, i);
                int[] postRight = Arrays.copyOfRange(postOrder, i, postOrder.length - 1);
                Node rootLeft = createTreeByInAndPost(inLeft, postLeft);
                Node rootRight = createTreeByInAndPost(inRight, postRight);
                node.setLeft(rootLeft);
                node.setRight(rootRight);
                break;
            }
        }
        return node;
    }
    
}
